package priority;

import java.util.*;

/**
 * 692、前k个高频单词
 */
public class Day21 {
    public List<String> topKFrequent(String[] words, int k) {
        // 1、把所以单词出现的次数计数，并且把字符串和次数放入到Map中
        Map<String,Integer> hash = new HashMap<>();
        for(String word : words) {
            hash.put(word,hash.getOrDefault(word,0) + 1);
        }

        // 2、创建一个堆，出现频率使用小根堆，相同频率比较字典顺序用大根堆
        // 堆里面存放Pair<String,Integer>这个类的值，相当于是 键-值
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b) -> {
                    if(a.getValue().equals(b.getValue())) {
                        // 这里是大根堆，比较的是字符，使用compareTo
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue() - b.getValue();
                }
        );

        // 3、Top-k 的逻辑
        // 把 Map中的值放入 heap中
        for(Map.Entry<String,Integer> e : hash.entrySet()) {
            // 放入堆中
            heap.offer(new Pair<>(e.getKey(),e.getValue()));
            if(heap.size() > k) {
                heap.poll();
            }
        }

        // 4、把heap中的值放入到 List中
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            ret.add(heap.poll().getKey());
        }

        // 5、这里的ret是一个倒序，需要进行翻转
        Collections.reverse(ret);

        return ret;
    }
}
